package 树.B树;

import javafx.util.Pair;

public class BTree {
    class BTNode {
        int size;
        int[] key;
        BTNode[] sub;
        BTNode parent;

        BTNode(int m) {
            key = new int[m];
            sub = new BTNode[m + 1];
            size = 0;
        }
    }

    BTNode root;
    int M = 3;

    // 返回值的含义：
// 键值对中的key：表示元素所在的节点
// 键值对中的value：表示元素在该节点中的位置
// 当value为-1时，表示该元素在节点中不存在
    public Pair<BTNode, Integer> ﬁnd(int key) {
        BTNode cur = root;
        BTNode parent = null;
        while (cur != null) {
            int index = 0;
            while (index < cur.size) {
                if (key == cur.key[index])
                    return new Pair<BTNode, Integer>(cur, index);
                else if (key < cur.key[index]) // 在该节点的第index个孩子中查找
                    break;
                else
                    index++; // 在该节点中继续查找
            }

// 在cur节点的第index的孩子节点中找key
            parent = cur;
            cur = cur.sub[index];
        }
// 未找到key，索引返回-1
        return new Pair<BTNode, Integer>(parent, -1);
    }


    // 采用插入排序的思想插入在cur节点中插入key以及分列出的sub孩子
    void insertKey(BTNode cur, int key, BTNode sub) {
        int end = cur.size - 1;
        while (end >= 0 && key < cur.key[end]) {
// 将该位置元素以及其右侧孩子往右搬移一个位置

            cur.key[end + 1] = cur.key[end];
            cur.sub[end + 2] = cur.sub[end + 1];
            end--;
        }
// 插入元素和孩子节点，更size
        cur.key[end + 1] = key;
        cur.sub[end + 2] = sub;
        cur.size++;
        if (sub != null) sub.parent = cur;
    }


    boolean insert(int key) {
        if (null == root) {
            root = new BTNode(M);
            root.key[0] = key;
            root.size = 1;
            return true;
        }

// 查找当前元素的插入位置
// 如果返回的键值对的value不等于-1，说明该元素已经存在，则不插入
        Pair<BTNode, Integer> ret = ﬁnd(key);
        if (-1 != ret.getValue()) {
            return false;
        }
// 注意：在B-Tree中找到的待插入的节点都是叶子节点
        BTNode cur = ret.getKey();
        int k = key;
        BTNode sub = null; // 主要在分列节点时起作用
        while (true) {
            insertKey(cur, k, sub);

// 元素插入后，当前节点可以放的下，不需要分列
            if (cur.size < M) break;

// 新节点插入后，cur节点不满足B-Tree的性质，需要对节点进行分列
// 具体分列的方式
// 1. 找到节点的中间位置
// 2. 将中间位置右侧的元素以及孩子插入到分列的新节点中
// 3. 将中间位置的元素以及分列出的新节点向当前分列节点的双亲中继续插入
            int mid = (cur.size >> 1);

            BTNode newNode = new BTNode(M);
// 将中间位置右侧的所有元素以及孩子搬移到新节点中
            int i = 0;
            int index = mid + 1; // 中间位置的右侧
            for (; index < cur.size; ++index) {
// 搬移元素
                newNode.key[i] = cur.key[index];

// 搬移元素对应的孩子
                newNode.sub[i++] = cur.sub[index];

// 孩子被搬移走了，需要重新更新孩子双亲
                if (cur.sub[index] != null) cur.sub[index].parent = newNode;
            }

// 注意：孩子要比双亲多搬移一个newNode.subs[i] = cur.subs[index]; if(cur.subs[index] != null)
            cur.sub[index].parent = newNode;

// 更新newNode以及cur节点中剩余元素的个数
// cur中的i个元素搬移到了newNode中
// cur节点的中间位置元素还要继续向其双亲中插入newNode.size = i;
            cur.size = cur.size - i - 1;

            k = cur.key[mid];

// 说明分列的cur节点刚好是根节点
            if (cur == root) {
                root = new BTNode(M);

                root.key[0] = k;


                root.sub[0] = cur;
                root.sub[1] = newNode;
                root.size = 1;
                cur.parent = root;
                newNode.parent = root;
                break;
            } else {
// 继续向双亲中插入
            sub = newNode; cur = cur.parent;
            }
        }

        return true;
    }
}
